import collections


class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: Node
        :rtype: str
        """
        if not root:
            return ''
        now_layer = [root]
        s = ''
        for i, item in enumerate(now_layer):
            s += str(item.val)
            s += ','
        s += 'p,;'
        while now_layer:
            next_layer = collections.deque()
            for item in now_layer:
                childs = item.children
                for child in childs:
                    s += str(child.val)
                    next_layer.append(child)
                    s += ','
                s += 'p,'
            now_layer = next_layer
            s += ';'
        return s

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: Node
        """
        if not data:
            return None
        data = data.split(';')
        root_val = int(data[0].split(',')[0])
        root = Node(root_val, [])
        now_layer = [root]
        for layer in data[1:-1]:
            index = 0
            next_s = layer.split(',')[: - 1]
            next_layer = collections.deque()
            for item in next_s:
                if item == 'p':
                    index += 1
                else:
                    val = int(item)
                    node = Node(val, [])
                    next_layer.append(node)
                    now_layer[index].children.append(node)
            now_layer = next_layer
        return root


cod = Codec()
s = '1,p,;'
tree = cod.deserialize(s)